from typing import List


class NumCount:

    def __init__(self, minNum, maxNum, numCount, count):
        self.count = count
        self.numCount = numCount
        self.maxNum = maxNum
        self.minNum = minNum

    def get_key(self):
        return str(self.numCount) + "_" + str(self.maxNum) + "_" + str(self.minNum)


class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        dp = []
        resp = {}
        allCount = 0
        for num in nums:
            for numCount in dp:
                if numCount.numCount == 1:
                    if numCount.minNum < num:
                        newKey = str(numCount.numCount + 1) + "_" + str(num) + "_" + str(numCount.minNum)
                        if newKey not in resp:
                            c = NumCount(numCount.minNum, num, numCount.numCount + 1, numCount.count)
                            resp[newKey] = c
                        else:
                            resp[newKey].count += numCount.count
                elif numCount.numCount == 2:
                    if numCount.minNum < num < numCount.maxNum:
                        newKey = str(numCount.numCount + 1) + "_" + str(numCount.maxNum) + "_" + str(numCount.minNum)
                        if newKey not in resp:
                            c = NumCount(numCount.minNum, numCount.maxNum, numCount.numCount + 1, numCount.count)
                            resp[newKey] = c
                        else:
                            resp[newKey].count += numCount.count
                elif numCount.numCount == 3:
                    if numCount.maxNum < num:
                        allCount += numCount.count

                newKey = numCount.get_key()
                if newKey not in resp:
                    resp[newKey] = numCount
                else:
                    resp[newKey].count += numCount.count

            newKey = "1_" + str(num)
            resp[newKey] = NumCount(num, num, 1, 1)

            dp = []
            # 转成dp
            for k in resp.keys():
                dp.append(resp[k])
            resp = {}
            # print(num)
            # for d in dp:
            #     print(d.get_key(), d.minNum, d.maxNum, d.numCount, d.count)
            # print()

        return allCount


if __name__ == '__main__':
    nums = [1, 3, 2, 4, 5]
    # nums = [2, 5, 3, 1, 4]
    # k = 1
    s = Solution()

    print(s.countQuadruplets(nums))
